//树的层次遍历及一般队列
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  20
typedef int Elemtype;
typedef struct BiTNode{
    Elemtype data;
    struct BiTNode *lchild;
    struct BiTNode * rchild;
}BiTNode,*BiTree;

void visit(Elemtype data){
    printf("  %d  ",data);
}

typedef struct node
{
    BiTNode* data;
    struct node *next;
}node;

typedef struct Queue{
    node *front;
    node *rear;
}Queue;

node* initNode(){
    node *n = (node*)malloc(sizeof(node));
    return n; 
}

Queue* initQueue(){
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

int isEmpty(Queue *q){
    if(q->front ==NULL){
        return 1;
    }
    return 0;
}
//入队
void EnQueue(Queue*q,BiTNode*data){
    node *n = initNode();
    n->data = data;n->next = NULL;
    if(isEmpty(q)){
        q->front = n;
        q->rear = n;
    }else{
        q->rear->next = n;
        q->rear = n;
    }

}
//出队
BiTNode * DeQueue(Queue *q){
    node *n = q->front;
    if(isEmpty(q)){
        return NULL;
    }
    BiTNode* res = n->data;
    if(q->front == q->rear){
        q->front = NULL;
        q->rear = NULL;
    }else{
        q->front = q->front->next;
    }
    free(n);
    return res;

}

void levelTraverse(BiTree T){
        Queue *Q = initQueue();
        if(T!=NULL){
            EnQueue(Q,T);
        }
        while (!isEmpty(Q))
        {
           BiTNode*e = DeQueue(Q);
           visit(e->data);
           if(e->lchild!=NULL){
            EnQueue(Q,e->lchild);
           }
           if(e->rchild!=NULL){
            EnQueue(Q,e->rchild);
           }
        }
}


//通过中序遍历和先序遍历来创建二叉树
BiTNode * createBiTree(Elemtype preOrderarr[],int preFirst,int preLast,
 Elemtype inOrderarr[],int inFirst , int inLast){

        if(preFirst > preLast){
            return NULL;
        }
        BiTNode * root = (BiTNode *)malloc(sizeof(BiTNode));
        root->data = preOrderarr[preFirst];
        int rootIndex; //寻找根节点在中序序列的索引
        for ( rootIndex = inFirst; rootIndex <= inLast; rootIndex++)
        {
           if(root->data == inOrderarr[rootIndex]){
                break;
           }
        }
        BiTNode * lchild = createBiTree(preOrderarr,preFirst+1,preFirst+rootIndex-inFirst,
        inOrderarr,inFirst,rootIndex-1);
        BiTNode * rchild = createBiTree(preOrderarr,preFirst+rootIndex-inFirst+1,preLast,
        inOrderarr,rootIndex+1,inLast);
        root->lchild = lchild;
        root->rchild = rchild;
        return root;
}
int main(){
    int preArr[MAXSIZE] = {1,2,4,5,7,3,6};
    int inArr[MAXSIZE] = {4,2,7,5,1,3,6}; 
    int levelArr[MAXSIZE] = {1,2,3,4,5,6,7}; 
    BiTree T =  createBiTree(preArr,0,6,inArr,0,6);
    levelTraverse(T);
   
}
